package algorithm.niuke;

public class 盈利计划 {
    /**
     * 帮派里有 G 名成员，他们可能犯下各种各样的罪行。
     * 
     * 第 i 种犯罪会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。
     * 
     * 让我们把这些犯罪的任何子集称为盈利计划，该计划至少产生 P 的利润。
     * 
     * 有多少种方案可以选择？因为答案很大，所以返回它模 10^9 + 7 的值。
     * 
     * 输入：G = 5, P = 3, group = [2,2], profit = [2,3] 输出：2 解释： 至少产生 3
     * 的利润，该帮派可以犯下罪 0 和罪 1 ，或仅犯下罪 1 。 总的来说，有两种方案。
     * 
     * 输入：G = 10, P = 5, group = [2,3,5], profit = [6,7,8] 输出：7 解释： 至少产生 5
     * 的利润，只要他们犯其中一种罪就行，所以该帮派可以犯下任何罪行 。 有 7
     * 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。
     * 
     * 提示：
     * 
     * 1 <= G <= 100 <br>
     * 0 <= P <= 100 <br>
     * 1 <= group[i] <= 100 0 <= profit[i] <= 100 <br>
     * 1 <= group.length = profit.length <= 100 <br>
     */
    boolean log = true;

    public int profitableSchemes(int G, int P, int[] group, int[] profit) {
        /**
         * 思路：借鉴0-1背包问题 对于第i条犯罪记录，能够产生利益j的方法总数为 method[j] +=
         * method[j-profit[i]]，但是由于需要注意人数 ，如果达到本次总利益有k人参与，那么 method[j][k] +=
         * method[j-profit[i]][k-group[i]]
         */
        int maxProfit = 0;
        int maxPersonNum = 0;
        for (int pro : profit) {
            maxProfit += pro;
        }
        if (maxProfit < P) {
            return 0;
        }
        maxProfit = P;// 对于超过P的利益方案统一为P
        for (int g : group) {
            maxPersonNum += g;
        }
        long[][] method = new long[maxProfit + 5][maxPersonNum + 5];
        int mod = 1000000007;

        for (int i = 0; i < group.length; i++) {
            for (int k = maxPersonNum - group[i]; k > 0; k--) {
                int newG = k + group[i];
                for (int j = maxProfit; j >= 0; j--) {
                    int newProfit = Math.min(j + profit[i], maxProfit);
                    method[newProfit][newG] += method[j][k];
                    method[newProfit][newG] %= mod;
                }
            }

            method[profit[i] > maxProfit ? maxProfit : profit[i]][group[i]] += 1;// 仅犯第i条罪行
        }
        int total = 0;
        for (int i = 0; i <= G && i <= maxPersonNum; i++) {
            total += method[P][i];
            total %= mod;
        }
        return total;
    }

    public int profitableSchemes2(int G, int P, int[] group, int[] profit) {
        int MOD = 1_000_000_007;
        int N = group.length;
        long[][][] dp = new long[2][P + 1][G + 1];
        dp[0][0][0] = 1;

        for (int i = 0; i < N; ++i) {
            int p0 = profit[i]; // the current crime profit
            int g0 = group[i]; // the current crime group size

            long[][] cur = dp[i % 2];
            long[][] cur2 = dp[(i + 1) % 2];

            // Deep copy cur into cur2
            for (int jp = 0; jp <= P; ++jp)
                for (int jg = 0; jg <= G; ++jg)
                    cur2[jp][jg] = cur[jp][jg];

            for (int p1 = 0; p1 <= P; ++p1) { // p1 : the current profit
                // p2 : the new profit after committing this crime
                int p2 = Math.min(p1 + p0, P);
                for (int g1 = 0; g1 <= G - g0; ++g1) { // g1 : the current group
                                                       // size
                    // g2 : the new group size after committing this crime
                    int g2 = g1 + g0;
                    cur2[p2][g2] += cur[p1][g1];
                    cur2[p2][g2] %= MOD;
                }
            }
        }

        // Sum all schemes with profit P and group size 0 <= g <= G.
        long ans = 0;
        for (long x : dp[N % 2][P])
            ans += x;

        return (int) ans;
    }

    public static void main(String[] args) {
        test3();
    }

    static void test3() {
        int g = 100;
        int p = 100;
        int[] group = { 2, 5, 36, 2, 5, 5, 14, 1, 12, 1, 14, 15, 1, 1, 27, 13, 6, 59, 6, 1, 7, 1, 2, 7, 6, 1, 6, 1, 3,
                1, 2, 11, 3, 39, 21, 20, 1, 27, 26, 22, 11, 17, 3, 2, 4, 5, 6, 18, 4, 14, 1, 1, 1, 3, 12, 9, 7, 3, 16,
                5, 1, 19, 4, 8, 6, 3, 2, 7, 3, 5, 12, 6, 15, 2, 11, 12, 12, 21, 5, 1, 13, 2, 29, 38, 10, 17, 1, 14, 1,
                62, 7, 1, 14, 6, 4, 16, 6, 4, 32, 48 };
        int[] profit = { 21, 4, 9, 12, 5, 8, 8, 5, 14, 18, 43, 24, 3, 0, 20, 9, 0, 24, 4, 0, 0, 7, 3, 13, 6, 5, 19, 6,
                3, 14, 9, 5, 5, 6, 4, 7, 20, 2, 13, 0, 1, 19, 4, 0, 11, 9, 6, 15, 15, 7, 1, 25, 17, 4, 4, 3, 43, 46, 82,
                15, 12, 4, 1, 8, 24, 3, 15, 3, 6, 3, 0, 8, 10, 8, 10, 1, 21, 13, 10, 28, 11, 27, 17, 1, 13, 10, 11, 4,
                36, 26, 4, 2, 2, 2, 10, 0, 11, 5, 22, 6 };
        盈利计划 run = new 盈利计划();
        // 692206787
        System.out.println(run.profitableSchemes(g, p, group, profit));
    }

    static void test2() {
        int g = 10;
        int p = 5;
        int[] group = { 2, 3, 5 };
        int[] profit = { 6, 7, 8 };
        盈利计划 run = new 盈利计划();
        // 896938
        System.out.println(run.profitableSchemes(g, p, group, profit));
    }

    static void test1() {
        int g = 10;
        int p = 100;
        int[] group = { 8, 8, 7, 4, 3, 1, 1, 6, 11, 3, 1, 7, 6, 9, 9, 1, 8, 9, 3, 10, 10, 8, 7, 6, 9, 10, 6, 2, 2, 6, 9,
                7, 5, 6, 2, 1, 2, 10, 11, 6, 8, 9, 9, 8, 11, 6, 2, 2, 4, 5, 1, 2, 1, 11, 3, 2, 11, 7, 11, 4, 5, 7, 6, 9,
                6, 7, 10, 10, 9, 10, 10, 8, 8, 6, 9, 8, 5, 1, 2, 5, 10, 1, 4, 2, 1, 5, 1, 3, 6, 6, 10, 6, 2, 3, 2, 1, 9,
                6, 6, 4 };
        int[] profit = { 23, 36, 94, 35, 73, 7, 65, 25, 22, 4, 62, 62, 12, 18, 89, 62, 2, 66, 85, 94, 73, 31, 56, 95,
                71, 91, 53, 75, 100, 47, 68, 4, 64, 52, 97, 8, 52, 32, 98, 64, 2, 64, 33, 21, 52, 44, 41, 50, 59, 40,
                48, 47, 39, 9, 100, 1, 43, 94, 63, 23, 21, 92, 36, 69, 100, 8, 75, 16, 79, 98, 72, 83, 70, 11, 3, 41,
                91, 18, 17, 76, 71, 58, 71, 62, 34, 49, 58, 59, 90, 84, 12, 43, 27, 60, 47, 89, 31, 14, 11, 15 };
        盈利计划 run = new 盈利计划();
        // 896938
        System.out.println(run.profitableSchemes(g, p, group, profit));
    }
}
